package 代码随想录.回溯.b;

import java.util.ArrayList;
import java.util.List;

public class a39组合总和 {

    public static List<List<Integer>> res;
    public static List<Integer> cur;

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        System.out.println(solution.combinationSum(candidates, target));
    }

    static class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            res = new ArrayList<>();
            cur = new ArrayList<>();
            int sum = 0;
            int index = 0;
            backtracking(candidates, index, sum, target);
            return res;
        }

        private void backtracking(int[] candidates, int index, int sum, int target) {
            if (sum > target) {
                return;
            }
            if (sum == target) {
                res.add(new ArrayList<>(cur));
                return;
            }
            for (int i = index; i < candidates.length; i++) {
                cur.add(candidates[i]);
                backtracking(candidates, i, sum + candidates[i], target);
                cur.remove(cur.size() - 1);
            }
        }

    }
}
